package bitSet;

public class MyBitSet {
    private byte[] elem;
    private int usedSize;

    public MyBitSet() {
        this.elem = new byte[2];
    }

    public MyBitSet(int n) {
        this.elem = new byte[n/8 + 1];
    }

    /**
     * 将元素存储在位图中
     * @param val val
     */
    public void set(int val){
        if(val < 0){
            throw new ArithmeticException();
        }
        int location = val / 8;
        // 扩容
        if (location >= elem.length){
            byte[] newElem = new byte[location + 1];
            System.arraycopy(elem, 0, newElem, 0, elem.length);
            elem = newElem;
        }
        int index = val % 8;
        if ((elem[location] & (1 << index)) == 0){
            elem[location] |= (byte)(1 << index);
            usedSize++;
        }
    }

    /**
     * 判断某元素是否存在
     * @param val val
     * @return boolean
     */
    public boolean get(int val){
        int location = val / 8;
        if (location >= elem.length) {
            return false;
        }
        int index = val % 8;
        return ((elem[location] >> index) & 1) == 1;
    }

    /**
     * 重置某一位为 0
     * @param val val
     */
    public void reSet(int val){
        int location = val / 8;
        if(location >= elem.length){
            return;
        }
        int index = val % 8;
        elem[location] &= (byte)(~(1 << index));
    }

    public int getUsedSize(){
        return usedSize;
    }

    /**
     * 使用位图进行排序并去重
     * @return 排序后的数组
     */
    public int[] sort(){
        int[] array = new int[elem.length * 8];
        int cur = 0;
        for (int i = 0; i < elem.length; i++) {
            for (int j = 0; j < 8; j++) {
                if(((elem[i] >> j) & 1) == 1){
                    array[cur++] = i * 8 + j;
                }
            }
        }
        int[] res = new int[cur];
        System.arraycopy(array, 0, res, 0, cur);
        return res;
    }
}
